This present invention relates generally to voice-over-packet-network and similar time-critical packet transmission, and more particularly to systems and methods for interleaving time-critical packets with lower-priority packets on a common data link without inducing significant jitter and/or delay in the time-critical packets.
Packet-switched networks route data from a source to a destination in packets. A packet is a relatively small sequence of digital symbols (e.g., several tens of binary octets up to several thousands of binary octets) that contains a payload and one or more headers. The payload is the information which the source wishes to send to the destination. The headers contain information about the nature of the payload and its delivery. For instance, headers can contain a source address, a destination address, data length and data format information, data sequencing or timing information, flow control information, and error correction information.
A packet""s payload can consist of just about anything that can be conveyed as digital information. Some examples are e-mail, computer text, graphic, and program files, web browser commands and pages, and communication control and signaling packets. Other examples are streaming audio and video packets, including real-time bidirectional audio and/or video conferencing. In Internet Protocol (IP) networks, a two-way (or multipoint) audio conference that uses packet delivery of audio is usually referred to as Voice over IP, or VoIP.
The urgency with which a given packet should be delivered depends to a great extent on the type of payload. E-mail and background file transfers are among the least urgent, as delays of minutes can usually easily be tolerated. On the other end of the spectrum, VoIP packets typically must be delivered within a few hundred milliseconds of their creation, or VoIP call quality begins to degrade noticeably. Other relatively high-priority packets can include data link flow control packets and network node status packets.
Since high-priority packets and low-priority packets must share the packet network, various schemes have been proposed to provide fair allocation of network resources between the two. For instance, FIG. 1 illustrates a portion of a device 20, e.g., implemented on a computer, that multiplexes VoIP packets and other data packets onto a common data link using a priority queuing mechanism. The VoIP packets are created by digitally encoding a voice capture channel (e.g., from a microphone or headset) using an AID (analog-to-digital) converter 22 and a voice encoder 26. Data packets are received from other applications running on the computer, e.g., a web-browser, e-mail application, or networked file system application.
Device 20 uses two packet queues. A time-critical-packet queue 28 queues VoIP packets as they are created. A data packet queue 36 queues lower-priority packets. Note that in FIG. 1, data packets pass through an optional data packet fragmenter 34, which segments large data packets into sequences of smaller data packets before submission to queue 36. Note also that signal packets from controller 24 are submitted to data packet queue 36. The signal packets provide overall coordination of VoIP call setup and termination, among other things, and may optionally be placed in queue 28.
Packet scheduler 30 multiplexes packets from queues 28 and 36 to data link interface 32. Under one prior art method of operation, scheduler 30 selects time-critical packets from queue 28 until queue 28 is emptied. When queue 28 is empty, scheduler 30 then selects packets from data packet queue 36. When queue 28 receives one or more additional time-critical packets, scheduler 30 switches back to queue 28 until that queue is once again empty.
The priority operation of scheduler 30 can be better understood with reference to the timing diagrams of FIGS. 2, 3, and 4. Referring first to FIG. 2, a single talkspurt on the voice capture channel is represented. The overall duration of the talkspurt is tTS1.
Voice encoder 26 groups voice samples from A/D converter 22 into voice sample blocks 1-1, 1-2, . . . , 1-8. Each sample block represents the same fixed number of voice samples, e.g., 80 samples, 240 samples, etc. Because the number of samples is fixed, block 1-8 extends past the end of the talkspurt in order to take in the appropriate number of samples.
Voice encoder 26 encodes each sample block into a voice packet. Simple encoders may do no more than place the entire sample block in a packet payload and attach addressing headers. More sophisticated encoders may compress the sample block using a variety of known coding techniques. In either case, the encoder cannot place a voice packet in packet queue 28 until sometime after the entire sample block is received at encoder 26xe2x80x94if sophisticated coding must also take place, additional delay may occur while the data is compressed. FIG. 2 illustrates the packet formation delay, tPF, as the time between when the first sample of a sample block is generated and when the packet corresponding to that sample block is queued.
When the time-critical packets do not have to compete for data link bandwidth (and the bandwidth of the channel is large compared to packet size), total packet transmission delay is not much greater than packet formation delay. Packet transmission delay, tTX, is the time between when the first sample of a sample block is generated and when transmission of the packet corresponding to that sample block has completed.
It is believed to have been heretofore unrecognized that time-critical packet transmission can be negatively affected, even with priority queuing. FIG. 3 shows packet transmission delay when two data packets are placed in data queue 28 shortly after voice packet VP1.1 is placed in queue 26. Once VP1.1 has been placed on the data link, queue 26 is empty. Scheduler 30 thus checks queue 36, finds data packet DP1 waiting, and selects that data packet for transmission. While the data packet is transmitting, voice packets VP1.2, VP1.3, and VP1.4 arrive at queue 26. Thus, a four-packet delayed xe2x80x9cburstxe2x80x9d of voice packets occurs at the end of data packet DP 1 transmission. With queue 26 once again empty, data packet DP2 from queue 36 is selected for transmission, causing another four-packet burst of voice packets to occur. In addition to the voice sample xe2x80x9cburstingxe2x80x9d phenomenon, data packet transmission has caused the transmission delay tTX for voice sample block 1-2, for example, to be substantially longer than the comparable delay in FIG. 2.
FIG. 4 shows the same scenario as FIG. 3, but using data packet fragmenter 34 to segment the two data packets of FIG. 3 into eight smaller data packets. Although this tends to improve the regularity of voice packet transmission and lessen the average voice packet transmission delay, the problem is not completely cured.
The disclosed embodiments address the interleaving of time-critical packets, such as VoIP packets, with lower-priority packets on a common data link. It has now been recognized that priority queuing can cause the time-critical packet jitter and absolute latency problems shown in FIG. 3xe2x80x94particularly on low-speed data links where the transmit time for a maximum transmission unit (MTU) data packet is on the order of (or larger than) the time spacing between consecutive voice packets. Furthermore, is has also now been recognized that an approach different from data packet fragmentation is also desirable. Not only does fragmentation not completely diminish the negative effects of priority queuing, but data packet fragmentation is generally undesirable, often difficult, and sometimes impossible to achieve.
In general, the disclosed embodiments determine when lower-priority packets can be sent with a low probability of introducing jitter or latency in a time-sensitive packet data stream. The embodiments take advantage of several characteristics of time-sensitive packet data. One, most packet voice and/or video systems generate packets at a fairly predictable maximum rate. Second, many such systems decrease their rate substantially when the voice or video is highly compressiblexe2x80x94i.e., during silent intervals or speech pauses (voice) and during periods of low motion content (video). The disclosed embodiments leverage these characteristics to predict the best times for interleaving data packets with voice or video packet streams.
In one aspect of the invention, a method of interleaving time-critical packets with lower-priority packets on a common data link is disclosed. Time-critical-packet arrival statistics are maintained. Then, when a lower-priority packet becomes available for transmission across the data link, the transmit time required for transmission of that packet is estimated. Based on the time-critical packet arrival statistics and the estimated transmit time for the lower-priority packet, a prediction is made. The prediction assesses whether the lower-priority packet can be submitted for transmission across the data link without causing substantial delay to a time-critical packet that is not yet available for transmission across the data link. When transmission at the current time is deemed acceptable, the lower-priority packet is supplied to the data link; otherwise, the lower-priority packet is parked, and the predicting step is performed again at a later time.
In another aspect of the invention, a packet data transmitting device is disclosed. The device comprises a data link interface, a lower-priority-packet queue to queue lower-priority packets awaiting submission to the data link interface, and a time-critical-packet queue to queue time-critical packets awaiting submission to the data link interface. The device further comprises a time-critical-packet arrival prediction mechanism to provide a prediction of the next time-critical packet""s arrival time, and a packet transmit time estimator to provide an estimate of a packet""s transmit time. The device also comprises a packet scheduler to interleave submission, to the data link interface, of the lower-priority packets and the time-critical packets. The scheduler receives predictions from the time-critical-packet arrival prediction mechanism and transmit time estimates from the packet transmit time estimator. The scheduler selects a packet from the lower-priority-packet queue for submission to the data link interface when that packet""s transmission can be completed without causing substantial delay to a time-critical-packet that is not yet in the time-critical-packet queue.